class Solution {
public:
    int ans[40];
    int fib(int n) {
        if(n == 0)  return 0;
        if(n == 1)  ans[n] = 1;
        else if(n <= 4) ans[n] = n - 1;
        if(ans[n])  return ans[n];
        ans[n] = fib(n - 1) + fib(n - 2);
        return ans[n];
    }
};